#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0
#define ok 1
#define error 0
#define overflow -2
#define null 0

#define MAX_LEN    10
#define LARGE    999

typedef struct graph
{
    int a[MAX_LEN];
    int b[MAX_LEN];
    int h[MAX_LEN];
    char vexs[MAX_LEN];
    int vexnum, arcnum;
    int kind;
    int arcs[MAX_LEN][MAX_LEN];
}graph;

typedef struct node
{
    int adjvex;
    int info;
    struct node *next;
}edgenode;

typedef struct vexnode
{
    int id;
    char data;
    edgenode *link;
}vexnode;

typedef struct adjlist
{
    vexnode adjs[MAX_LEN];
    int vexnum, arcnum;
    int kind;
}adjlist;

typedef struct qnode
{
    int data;
    struct qnode *next;
}linkqlist;

typedef struct 
{
    linkqlist *front;
    linkqlist *rear;
}linkqueue;

typedef struct 
{
    int stack[MAX_LEN];
    int top;
}stack;

int cnull = -1;
graph g;
adjlist adjl;
stack *t;
stack *s;
linkqueue *q;

graph print_adjmatrix(graph g)
{
    int i, j;
    
    printf("vertex\t");

    for (i = 0; i < g.vexnum; i++)
        printf("%4c", g.vexs[i]);
    printf("\n");

    for (i = 0; i < g.vexnum; i++) {
        printf("%4c \t", g.vexs[i]);
        for (j = 0; j < g.vexnum; j++)
            printf("%4d", g.arcs[i][j]);
        printf("\n");
    }

    return g;
}

void create_1(graph g)
{
    int i, j, k, c = 0;

    for (i = 0; i < g.vexnum; i++)
        for (j = 0; j < g.vexnum; j++)
        g.arcs[i][j] = c;

    for (k = 0; k < g.arcnum; k++)
        g.arcs[g.a[k] - 1][g.b[k] - 1] = 1;

    print_adjmatrix(g);
}

void create_2(graph g)
{
    int i, j, k, c = 0;

    for (i = 0; i < g.vexnum; i++)
        for (j = 0; j < g.vexnum; j++)
        g.arcs[i][j] = c;

    for (k = 0; k < g.arcnum; k++) {
        g.arcs[g.a[k] - 1][g.b[k] - 1] = 1;
        g.arcs[g.b[k] - 1][g.a[k] - 1] = 1;
    }

    print_adjmatrix(g);
}

graph create_3(graph g)
{
    int i, j, k, c = 999;

    for (i = 0; i < g.vexnum; i++)
        for (j = 0; j < g.vexnum; j++)
        g.arcs[i][j] = c;

    for (k = 0; k < g.arcnum; k++)
        g.arcs[g.a[k] - 1][g.b[k] - 1] = g.h[k];

    print_adjmatrix(g);
    
    return g;
}

graph create_4(graph g)
{
    int i, j, k, c = 999;

    for (i = 0; i < g.vexnum; i++)
        for (j = 0; j < g.vexnum; j++)
        g.arcs[i][j] = c;

    for (k = 0; k < g.arcnum; k++) {
        g.arcs[g.a[k] - 1][g.b[k] - 1] = g.h[k];
        g.arcs[g.b[k] - 1][g.a[k] - 1] = g.h[k];
    }

    print_adjmatrix(g);

    return g;
}

void creategraph(graph g)
{
    switch(g.kind) {
        case 1:
            create_1(g); break;
        case 2:
            create_2(g); break;
        case 3:
            create_3(g); break;
        case 4:
            create_4(g); break;
        default:
            printf("Error\n");
    }
}

adjlist createlist(graph g, adjlist adjl)
{
    int i;
    edgenode *p;

    if (g.kind == 1 || g.kind == 3) {
        for (i = 0; i < adjl.arcnum; i++) {
            p = (edgenode *)malloc(sizeof(edgenode));
            p->adjvex = g.b[i];
            p->info = g.h[i];
            p->next = adjl.adjs[g.a[i] - 1].link;
            adjl.adjs[g.a[i] - 1].link = p;
        }
    }

    if (g.kind == 2 || g.kind == 4) {
        for (i = 0; i < adjl.arcnum; i++) {
            p = (edgenode *)malloc(sizeof(edgenode));
            p->info = g.h[i];
            p->adjvex = g.b[i];
            p->next = adjl.adjs[g.a[i] - 1].link;
            adjl.adjs[g.a[i] - 1].link = p;

            p = (edgenode *)malloc(sizeof(edgenode));
            p->info = g.h[i];
            p->adjvex = g.a[i];
            p->next = adjl.adjs[g.b[i] - 1].link;
            adjl.adjs[g.b[i] - 1].link = p;
        }
    }

    printf("lin jie biao wei : \n");
    for (i = 0; i < g.vexnum; i++) {
        printf("[%d, %c] => ", i + 1, adjl.adjs[i].data);
        p = adjl.adjs[i].link;
        while (p != NULL) {
            printf("[%c, %d]-->", adjl.adjs[(p->adjvex) - 1].data, p->info);
            p = p->next;
        }
        printf("\n");
    }

    return adjl;
}

void initqueue(linkqueue *p)
{
    p->front = (linkqlist *)malloc(sizeof(linkqlist));
    p->rear = p->front;
    (p->front)->next = NULL;
}

int empty(linkqueue *q)
{
    int v;
    
    if (q->front == q->rear)
        v = true;
    else
        v = false;

    return v;
}

int addqueue(linkqueue *q, int e)
{
    q->rear->next = (linkqlist *)malloc(sizeof(linkqlist));
    q->rear = q->rear->next;

    if (!q->rear)
        return -1;
    q->rear->data = e;
    q->rear->next = NULL;

    return 0;
}

int delqueue(linkqueue *q)
{
    linkqlist *p;
    int e;

    if (q->front == q->rear)
        printf("the linklist is overflow\n");
    else
        p = (q->front)->next;
    (q->front)->next = p->next;
    e = p->data;

    if (q->rear == p)
        q->rear = q->front;
    free(p);

    return e;
}

/* depth first search */
void dfs(int i, adjlist adjl)
{
    edgenode *p;
    int j;
    int visited[MAX_LEN];

    for (j = 0; j < adjl.vexnum; j++)
        visited[j] = 0;
    printf("%4c->", adjl.adjs[i-1].data);
    visited[i-1] = 1;
    p = adjl.adjs[i - 1].link;
    while (p != NULL) {
        if (visited[(p->adjvex) - 1] != 1)
            dfs(p->adjvex, adjl);
        p = p->next;
    }
}

/* guangDu first search */
void bfs(int i, adjlist adjl)
{
    edgenode *p;
    int j;
    int visited[MAX_LEN];

    for (j = 0; j < adjl.vexnum; j++)
        visited[j] = 0;

    initqueue(q);
    printf("%4c->", adjl.adjs[i-1].data);
    visited[i-1] = 1;
    addqueue(q, i);
    while (!empty(q)) {
        i = delqueue(q);
        p = adjl.adjs[i-1].link;
        while (p != NULL) {
            if (visited[(p->adjvex) - 1] == 0) {
                printf("%4c->", adjl.adjs[p->adjvex - 1].data);
                visited[(p->adjvex) - 1] = 1;
                addqueue(q, p->adjvex);
                p = p->next;
            }
        }
    }
}

int initstack(stack *s)
{
    s->top = 0;
    return 1;
}

int push(stack *s, int x)
{
    if (s->top == MAX_LEN)
        printf("the stack is overflow.\n");
    else {
        s->top = s->top + 1;
        s->stack[s->top] = x;
    }
}

int pop(stack *s)
{
    int y;

    if (s->top == 0)
        printf("the stack is empty!\n");
    else {
        y = s->stack[s->top];
        s->top = s->top -1;
    }

    return y;
}

int stackempty(stack *s)
{
    if (s->top == MAX_LEN)
        return 1;
    else
        return 0;
}

int topsort(adjlist adjl)
{
    int i, k, count;
    edgenode *p;

    printf("tuo pu sort is : \n");
    initstack(s);

    for (i = 0; i < adjl.vexnum; i++)
        if (adjl.adjs[i].id == 0)
            push(s, adjl.adjs[i].data);
    count = 0;
    while (!stackempty(s)) {
        i = pop(s);
        printf("%4c-->", adjl.adjs[i].data);
        ++count;
        for (p = adjl.adjs[i].link; p; p = p->next) {
            k = p->adjvex;
            if (!(--adjl.adjs[k-1].id))
                push(s, k - 1);
        }
    }

    if (count < adjl.vexnum) {
        printf("wang zhong you huan\n");
        return 0;
    }
    else
        return 1;
}

void prim(graph g)
{
    int i, j, k, min;
    int lowcost[MAX_LEN];
    int closet[MAX_LEN];

    printf("zui xiao shengchengshu de bian wei : \n");

    for (i = 1; i < g.vexnum; i++) {
        lowcost[i] = g.arcs[0][i];
        closet[i] = 1;
    }
    closet[1] = 0;
    j = 1;
    for (i = 1; i < g.vexnum; i++) {
        min = lowcost[j];
        k = i;
        for (j = 1; j < g.vexnum; j++)
            if (lowcost[j] < min && closet[j] != 0) {
                min = lowcost[j];
                k = j;
            }

            printf("(%c, %c), ", g.vexs[k-1], g.vexs[closet[k-1]]);
            closet[k] = 0;
            for (j = 1; j < g.vexnum; j++)
                if (g.arcs[k][j] < lowcost[j] && closet[j] != 0) {
                    lowcost[j] = g.arcs[k][j];
                    closet[j] = k;
                }
    }

}

int ve[MAX_LEN];
int vl[MAX_LEN];

int toporder(adjlist adjl, stack *t)
{
    int i, j, count, k;
    edgenode *p;

    initstack(s);
    initstack(t);
    for (i = 0; i < adjl.vexnum; i++)
        if (adjl.adjs[i].id == 0)
            push(s, i);

    count = 0; 
    for (i = 0; i < adjl.vexnum; i++)
        ve[i] = 0;
    while (!stackempty(s)) {
        j = pop(s);
        push(t, j);
        ++count;
        for (p = adjl.adjs[j].link; p; p = p->next) {
            k = p->adjvex;
            if (--adjl.adjs[k - 1].id == 0)
                push(s, k - 1);
            if (ve[j] + (p->info) > ve[k - 1])
                ve[k - 1] = ve[j] + p->info;
        }
    }
    if (count < adjl.vexnum)
        return error;
    else
        return ok;

}

int criticalpath(adjlist adjl)
{
    int i, j, k, dut, ee, el;
    edgenode *p;

    if (!toporder(adjl, t))
        return error;
    for (i = 0; i < adjl.vexnum; i++)
        vl[i] = ve[i - 1];
    printf("guanjian lujing wei: \n");

    while (!stackempty(t))
        for (j = pop(t), p = adjl.adjs[j].link; p; p = p->next) {
            k = p->adjvex;
            dut = p->info;
            if (vl[k] - dut < vl[j])
                vl[j] = vl[k] - dut;
        }
    for (j = 0; j < adjl.vexnum; j++)
        for (p = adjl.adjs[j].link; p; p = p->next) {
            k = p->adjvex;
            dut = p->info;
            ee = ve[j];
            el = vl[k-1] - dut;
            if (ee == el)
                printf("(%c, %c)-->", adjl.adjs[j].data, adjl.adjs[k - 1].data);
        }
}

void shortpath_dijkstra(graph g)
{
    int cost[MAX_LEN][MAX_LEN];
    int dist[MAX_LEN];
    int path[MAX_LEN];
    int s[MAX_LEN];
    int i, j, v0, min, u;

    printf("\n qing shu ru qidian de bian hao:");
    scanf("%d", &v0);
    v0--;
    for (i = 0; i < g.vexnum; i++) {
        for (j = 0; j < g.vexnum; j++)
            cost[i][j] = g.arcs[i][j];
    }
    for (i = 0; i < g.vexnum; i++) {
        dist[i] = cost[v0][i];
        if (dist[i] < LARGE && dist[i] > 0)
            path[i] = v0;
        s[i] = 0;
    }
    s[v0] = 1;
    for (i = 0; i < g.vexnum; i++) {
        min = LARGE;
        u = v0;
        for (j = 0; j < g.vexnum; j++)
            if (s[j] == 0 && dist[j] < min) {
                min = dist[j];
                u = j;
            }
        s[u] = 1;
        for (j = 0; j < g.vexnum; j++)
            if (s[j] == 0 && dist[u] + cost[u][j] < dist[j]) {
                dist[j] = dist[u] + cost[u][j];
                path[j] = u;
            }
    }

    printf("\n dingdian %d dao ge dingdian de zui duan lu jing chang du wei : \n", v0);
    for (i = 0; i < g.vexnum; i++)
        if (s[i] == 1) {
            u = i;
            while (u != v0) {
                printf("%4c <--", g.vexs[u]);
                u = path[u];
            }
            printf("%4c", g.vexs[u]);
            printf(":%d\n", path[i]);
        }
        else
            printf("%4c <--%4c: wu lujing\n", g.vexs[i], g.vexs[v0]);
}

void shortpath_floyd(graph g)
{
    int path[MAX_LEN][MAX_LEN];
    int short3[MAX_LEN][MAX_LEN];
    int i, j, k;

    for (i = 0; i < g.vexnum; i++)
        for (j = 0; j < g.vexnum; j++) {
            short3[i][j] = g.arcs[i][j];
            path[i][j] = 0;
        }

    printf("ge ding dian jian de zui duan lu jing :\n");
    for (k = 0; k < g.vexnum; k++)
        for (i = 0; i < g.vexnum; i++) {
            if (short3[i][j] > (short3[i][k] + short3[k][j])) {
                short3[i][j] = short3[i][k] + short3[k][j];
                path[i][j] = k;
            }
            printf("(%4c -> %4c) : %d", g.vexs[i-1], g.vexs[j-1], short3[i][j]);
        }
}


int    main()
{
    int a,i,j,k,h;
    printf("\n graph type : (1:you xiang tu 2:wu xiang tu 3:you xiang wang 4:wu xiang wang):");
    scanf("%d",&i);

    g.kind=i;
    adjl.kind=i;

    printf("input ding bian shu:");
    scanf("%d,%d",&i,&j);

    g.vexnum=i;
    adjl.vexnum=i;

    g.arcnum=j;
    adjl.arcnum=j;

    for (i=0;i<g.vexnum;i++) { 
        printf("di %d ge ding dian xinxi:",i+1);
        scanf("%s",&g.vexs[i]);
        adjl.adjs[i].data=g.vexs[i];
        adjl.adjs[i].link=NULL;
        adjl.adjs[i].id=0;
    }

    for (k=1;k<=g.arcnum;k++) {
        label:
            if (g.kind==1||g.kind==3)
                printf("di %d tiao bian de qidian zhongdian bianhao : ",k);
            else 
                printf("di %d tiao bian de liang ge ding dian de bian hao:",k);
            scanf("%d,%d",&i,&j);

            g.a[k-1]=i;g.b[k-1]=j;
            while (i<1||i>g.vexnum||j<1||j>g.vexnum) {
                printf("    bian hao chao chu fangwei, again");
                goto label;
            }
            if (g.kind==3||g.kind==4) {
                printf("\t gai bian de quan zhi:");
                scanf("%d",&h);
                g.h[k-1]=h;
            }
            else  g.h[k-1]=null;
            adjl.adjs[i].id++;
    }

    loop1:
        printf("\n1__lin jie zu zhen\n");
        printf("2__lin jie biao\n");
        printf("3__dfs\n");
        printf("4__bfs\n");
        printf("5__zui xiao shengcheng shu\n");
        printf("6__tuo pu jieguo\n");
        printf("7__guanjian lu jing\n");
        printf("8__cong mou ge yuan dian dao qiyu ge dingdian de zui duan lujing : \n");
        printf("9__mei yi dui ding dian zhijian de zui duan lu jing : \n");
        loop:printf("change grahp implement : \t");

    scanf("%d",&a);

    switch(a)
    {
        case 1:
            creategraph(g);
            break;
        case 2:
            createlist(g,adjl);
            break;
        case 3:
            printf("chu fu:");
            scanf("%d",&k);
            createlist(g,adjl);
            printf("\n == %d  == dfs:",k);
            dfs(k,adjl);
            break;
        case 4:
            printf("chu fu dian:");
            scanf("%d",&k);
            createlist( g,adjl);
            printf("\n== %d == bfs:",k);    
            bfs( k,adjl);
            break;
        case 5:
            if (g.kind==4) {
                create_4(g); prim(g);
            }
            else{
                printf("\t 5 ==== :\n");
                goto loop;
            }
            break;
        case 6:
            if (g.kind==1||g.kind==3) {
                createlist(g,adjl); 
                topsort(adjl);
            }
            else{
                printf("\t bu nend tuo pu piaxu :\n");
                goto loop;
            }
            break;
        case 7:
            if (g.kind==3) {
                createlist(g,adjl);
                criticalpath( adjl);
            }
            else{
                printf("\t not guanjian path:\n");
                goto loop;
            }
            break;
        case 8:
            if (g.kind==3)
            {
                create_3(g); 
                shortpath_dijkstra(g);
            }
            else{
                printf("\t not zui duan path :\n");
                goto loop;
            }
            break;
        case 9:
            if (g.kind==3) {
                create_3(g); 
                shortpath_floyd(g);
            }
            else{
                printf("\t not zui duan path :\n");
                goto loop;
            }
            break;
        default:
            printf(" \n\t*** wrong ***\n");
    }
    goto loop1;
}

